#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
using namespace std;

//namespace lh
//{
//	void test1()
//	{
//		vector<int> V;
//		V.push_back(1);
//		V.push_back(2);
//		V.push_back(3);
//		V.push_back(4);
//		vector<int>::iterator it = V.begin();
//		while (it != V.end())
//		{
//			cout << *it << ' ';
//			++it;
//		}
//		cout << endl;
//		//反向迭代器
//		vector<int>::reverse_iterator rit = V.rbegin();
//		while (rit != V.rend())
//		{
//			cout << *rit << ' ';
//			++rit;
//		}
//		cout << endl;
//	}
//
//	void TestVectorExpand()
//	{
//		size_t sz;
//		vector<int> v;
//		sz = v.capacity();
//		v.reserve(100);//提前将容量设置好，可以避免一遍插入一遍扩容
//		cout << "making v grow:\n";
//		for (int i = 0; i < 100; ++i)
//		{
//			v.push_back(i);
//			if (sz != v.capacity())
//			{
//				sz = v.capacity();
//				cout << "capacity changed: " << sz << endl;
//			}
//		}
//	}
//
//	void test2()
//	{
//		vector<int> v;
//
//		// set some initial content:
//		for (int i = 1; i < 10; i++)
//			v.push_back(i);
//
//		v.resize(5);
//		v.resize(8, 100);
//		v.resize(12);
//		cout << v.size() << endl;
//		cout << "v contains:";
//		for (size_t i = 0; i < v.size(); i++)
//			cout << ' ' << v[i];
//		cout << endl;
//	}
//
//	void test3()
//	{
//		vector<int> v{ 1,2,3,4 };//列表方式初始化，C++11新语法
//		size_t sz = v.capacity();
//		v.push_back(5);
//		v.push_back(6);
//		//v.pop_back();
//		v.push_back(7);
//
//		cout << v.capacity() << endl;
//		for (size_t i = 0; i < v.size(); i++)
//		{
//			cout << v[i] << ' ';
//		}
//		cout << endl;
//		vector<int>::iterator pos = find(v.begin(), v.end(), 3);
//		if (pos != v.end())
//		{
//			v.insert(pos, 0); 
//		}
//		cout << v.capacity() << endl;
//		//pos = find(v.begin(), v.end(), 3);
//		v.erase(pos);
//		for (size_t i = 0; i < v.size(); i++)
//		{
//			cout << v[i] << ' ';
//		}
//		cout << endl;
//
//	}
//};

namespace lh_test
{
	//BM4 合并两个排序数组
	//https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
	
	struct ListNode {
		int val;
		struct ListNode *next;
		ListNode(int x) :
				val(x), next(NULL) {
		}
	};
#include <iterator>
	class Solution {
	public:
		ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
			//判空
			if (pHead1 == nullptr || pHead2 == nullptr)
			{
				ListNode* empty_head;
				return empty_head = pHead1 == nullptr ? pHead2 : pHead1;
			}
			//表头结点
			ListNode* head = new ListNode(-1);
			//cur为遍历结点
			ListNode* cur = head;
			ListNode* tail = pHead2;
			while (pHead1 && pHead2)
			{
				//取较小值的结点
				if (pHead1->val <= pHead2->val)
				{
					cur->next = pHead1;
					//移动取值指针
					pHead1 = pHead1->next;
				}
				else {
					cur->next = pHead2;
					//移动取值指针
					pHead2 = pHead2->next;
				}
				//指针后移
				cur = cur->next;
			}
			//将剩余链表连在后面
			if (pHead1)
				cur->next = pHead1;
			if (pHead2)
				cur->next = pHead2;
			return head->next;
		}
	};
	void test1()
	{
		ListNode* node1 = new ListNode(1);
		ListNode* node2 = new ListNode(3);
		ListNode* node3 = new ListNode(5);

		node1->next = node2;
		node2->next = node3;

		ListNode* node4 = new ListNode(2);
		ListNode* node5 = new ListNode(4);
		ListNode* node6 = new ListNode(6);

		node4->next = node5;
		node5->next = node6;


		ListNode* cur = node1;
		ListNode* cur2 = node4;
		while (cur)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
		while (cur2)
		{
			cout << cur2->val << "->";
			cur2 = cur2->next;
		}
		cout << endl;

		ListNode* res = Solution().Merge(node1, node4);
		while (res)
		{
			cout << res->val << "->";
			res = res->next;
		}
		cout << endl;

		delete node1;
		delete node2;
		delete node3;
		delete node4;
		delete node5;
		delete node6;

		delete res;
		delete cur;
		delete cur2;
	}

	//BM5 合并k个已排序的链表
	//https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
	class Solution2 {
	public:
		ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
			//判空
			if (pHead1 == nullptr || pHead2 == nullptr)
			{
				ListNode* empty_head;
				return empty_head = pHead1 == nullptr ? pHead2 : pHead1;
			}
			//表头结点
			ListNode* head = new ListNode(-1);
			//cur为遍历结点
			ListNode* cur = head;
			ListNode* tail = pHead2;
			while (pHead1 && pHead2)
			{
				//取较小值的结点
				if (pHead1->val <= pHead2->val)
				{
					cur->next = pHead1;
					//移动取值指针
					pHead1 = pHead1->next;
				}
				else {
					cur->next = pHead2;
					//移动取值指针
					pHead2 = pHead2->next;
				}
				//指针后移
				cur = cur->next;
			}
			//将剩余链表连在后面
			if (pHead1)
				cur->next = pHead1;
			if (pHead2)
				cur->next = pHead2;
			return head->next;
		}

		//划分合并区间函数
		ListNode* divideMerage(vector<ListNode*>& lists, int left, int right)
		{
			if (left > right)
				return NULL;
			//中间一个情况
			else if (left == right)
				return lists[left];
			//从中间分成两段，再将合并好的两段合并
			int mid = (left + right) / 2;
			return Merge(divideMerage(lists, left, mid), divideMerage(lists, mid + 1, right));
		}

		ListNode* mergeKLists(vector<ListNode*>& lists) {
			//k个链表归并排序
			return divideMerage(lists, 0, lists.size() - 1);
		}
	};

	void test2()
	{
		ListNode* node1 = new ListNode(1);
		ListNode* node2 = new ListNode(2);

		node1->next = node2;

		ListNode* node3 = new ListNode(1);
		ListNode* node4 = new ListNode(4);
		ListNode* node5 = new ListNode(5);

		node3->next = node4;
		node4->next = node5;

		ListNode* node6 = new ListNode(6);

		ListNode* cur = node1;
		ListNode* cur2 = node3;
		while (cur)
		{
			cout << cur->val << "->";
			cur = cur->next;
		}
		cout << endl;
		while (cur2)
		{
			cout << cur2->val << "->";
			cur2 = cur2->next;
		}
		cout << endl;
		ListNode* cur3 = node6;
		while (cur3)
		{
			cout << cur3->val << "->";
			cur3 = cur3->next;
		}
		cout << endl;

		vector<ListNode*>list;
		list.push_back(node1);
		list.push_back(node3);
		list.push_back(node6);

		ListNode* res = Solution2().mergeKLists(list);
		while (res)
		{
			cout << res->val <<"->";
			res = res->next;
		}
		cout << endl;

		delete node1;
		delete node2;
		delete node3;
		delete node4;
		delete node5;
		delete node6;

		delete res;
		delete cur;
		delete cur2;
		delete cur3;
	}
};


int main()
{
	//lh::test1();
	//lh::TestVectorExpand();
	//lh:: test2();
	//lh::test3();
	cout << "BM4" << endl;
	lh_test::test1();
	cout << "BM5" << endl;
	lh_test::test2();
	return 0;
}